import { testSort, measureSort } from "./utils";

function mergeSort(arr: number[]) {
  if (arr.length <= 1) {
    return arr;
  }

  const idx = Math.floor(arr.length / 2);
  const newLeftArr = mergeSort(arr.slice(0, idx))!;
  const newRightArr = mergeSort(arr.slice(idx))!;

  const result: number[] = [];
  let i = 0;
  let j = 0;
  while (i < newLeftArr.length && j < newRightArr.length) {
    if (newLeftArr[i] < newRightArr[j]) {
      result.push(newLeftArr[i]);
      i++;
    } else {
      result.push(newRightArr[j]);
      j++;
    }
  }

  if (i < newLeftArr.length) {
    result.push(...newLeftArr.slice(i));
  }
  if (j < newLeftArr.length) {
    result.push(...newRightArr.slice(j));
  }

  return result;
}



// 测试
testSort(mergeSort);
// 测试时间
measureSort(mergeSort, 100000);